package com.learn.algorlthm;

/**
 * @classname:
 * @Description:两个链表的第一个公共结点
 * @author: yfpu(fengpu.yang @ ucarinc.com)
 * @Date: 2018-08-14 16:23
 * 题目描述：
 * 输入两个链表，找出它们的第一个公共结点。
 */
public class Learn52 {

    /**
     * 解题思路
     * 设 A 的长度为 a + c，B 的长度为 b + c，其中 c 为尾部公共部分长度，可知 a + c + b = b + c + a。
     * <p>
     * 当访问 A 链表的指针访问到链表尾部时，令它从链表 B 的头部重新开始访问链表 B；同样地，当访问 B 链表
     * 的指针访问到链表尾部时，令它从链表 A 的头部重新开始访问链表 A。这样就能控制访问 A 和 B 两个链表的指针能同时访问到交点。
     */


    public static ListNode findFirstCommonNode(ListNode pHead1, ListNode pHead2) {
        if (pHead1 == null || pHead2 == null)
            return null;
        ListNode n1 = pHead1.next, n2 = pHead2.next;
        while (n1 != n2) {
            n1 = n1.next == null ? pHead2 : n1.next;
            n2 = n2.next == null ? pHead1 : n2.next;
        }
        return n1;
    }



    class ListNode {

        private int i;
        private ListNode next;

        public int getI() {
            return i;
        }

        public void setI(int i) {
            this.i = i;
        }

        public ListNode getNext() {
            return next;
        }

        public void setNext(ListNode next) {
            this.next = next;
        }
    }

}
